#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include"../../util/tool.h"

static int sortOrderArray[10];

int index_ = 0;

// 可以用简单的循环来做这个排序
void stackSortHelp(int * stackArray,int stackIndex,int * orderArray,int orderIndex,int length){

    if(orderIndex == length){

        for(int index = stackIndex;index >= 0;--index){

            sortOrderArray[index_++] = stackArray[index];
        }
        printf("sorted.\n");
        return;
    }
    // empty stackArray 空栈则压入栈
    if(stackArray[stackIndex] == -1){

        stackArray[stackIndex] = orderArray[orderIndex];
        orderIndex++;
    }
    // 如果大于栈顶元素则栈顶元素出栈 并将这个元素与下一个栈顶元素进行比较 直到一个适合的位置入栈
    else if(stackArray[stackIndex] < orderArray[orderIndex]){

        sortOrderArray[index_] = stackArray[stackIndex];
        index_++;
        // 栈顶元素是最后一个元素所以直接进行入栈操作
        if(stackIndex == 0){
            stackArray[stackIndex] = orderArray[orderIndex];
            orderIndex++;
        }else{         
            stackIndex--;
        }
    }
    // 小于或等于栈顶的元素则直接压入栈
    else if(stackArray[stackIndex] >= orderArray[orderIndex]){

        stackIndex++;
        stackArray[stackIndex] = orderArray[orderIndex];
        orderIndex++;
    }
    // 迭代处理
    stackSortHelp(stackArray,stackIndex,orderArray,orderIndex,length);

}
// 简单的栈排序
void stackSort(int * stackArray,int * orderArray,int number){

    // stackArray,stackIndex,orderArray,orderIndex,number
    stackSortHelp(stackArray,0,orderArray,0,number);
}

int
main(int argc,char * argv[]){

    int number = 10;
    int initValue = -1;
    int * orderArray = arrGen(number,NULL);
    int * stackArray = arrGen(number,&initValue);

    if(stackArray == NULL || orderArray == NULL){

        printf("stackArray or orderArray is NULL.\n");
        return EXIT_FAILURE;
    }

    number = 6;
    orderArray[0] = 1;
    orderArray[1] = 5;
    orderArray[2] = 2;
    orderArray[3] = 3;
    orderArray[4] = 5;
    orderArray[5] = 4;

    // printArray(stackArray,number);
    printArray(orderArray,number);
    stackSort(stackArray,orderArray,number);

    printArray(sortOrderArray,index_);

    free(stackArray);
    free(orderArray);
    return EXIT_SUCCESS;
}